def insertion_sort_nonincreasing(A):
    n=len(A)
    for j in xrange(1,n):
        key=A[j]
        i=j-1
        while i>=0 and A[i]<key: #相等元素插入后边
            A[i+1]=A[i]
            i=i-1
        A[i+1]=key
    return A

if __name__=='__main__':
    A=[11,5,2,6,77,23,8,4,123]
    print 'A=', A
    print 'result=', insertion_sort_nonincreasing(A)
